1. Field of the Invention
The present invention generally relates to data packet routing for a mobile ad hoc network, and more particularly, relates to an apparatus, method and system for a destination cached routing protocol for mobile ad hoc networks.
2. Description of the Prior Art
Mobile ad hoc networks may be utilized to form an internet or other network of “things”, in any given period of time and at any given location, and has no fixed topology and generally no fixed infrastructure. A mobile ad hoc network may be located anywhere, such as an airport waiting lounge, a subway station, a train car, an airplane, a restaurant, a store, a parking lot, a coffee shop, a night club, a theatre, a hotel lobby, etc. A mobile ad hoc network may be comprised of any type of mobile devices, typically referred to as nodes, and the composition of any such mobile ad hoc network is typically fluid and changing over time, as mobile devices enter or leave a mobile ad hoc network.
Mobile ad hoc networks typically transmit data between and among the various mobile nodes (devices) as data packets. In such a mobile ad hoc network, any mobile device may function as a host and also as a router, to not only receive and transmit data packets as a destination node or a source node, but also to act as an intermediate node and route data packets received from another, second device to a third device in the mobile ad hoc network.
Various problems exist in prior art routing protocols for such mobile ad hoc networks. When a source node has to transfer data to a destination node, a route discovery process commences, initiated by the source node, with Route Request (“RREQ”) packets being broadcast in the mobile ad hoc network. As the packet propagates in the network and is received by a plurality of nodes, each (intermediate) node adds its address into the RREQ packet and continues to broadcast the RREQ packet to successive nodes, until either the destination (or target) of the RREQ packet is found, or until another intermediate node is found that can supply a route to the destination. As a result, the RREQ packets grow in size, and such large packets tend to create congestion and delay in the network. In addition, breaking the larger RREQ packet into two or more smaller packets may cause corrupted data and/or dropped data, with subsequent retransmission further serving to increase congestion. A node may also receive many RREQ packets, which can lead to congestion in the node and loss of a data packet or a RREQ packet, thereby reducing reliability of the network.
Similarly, a destination node generates a Route Reply (“RREP”) packet for each received RREQ packet. The route included in the RREP packet is obtained by reversing the route that is specified in the RREQ packet. As the RREP packet moves following this route through intermediate nodes to the source node, the nodes receiving the RREP packet caches or otherwise saves the route from its address to the destination. The source node may receive many RREP packets, affording many alternative routes to reach the destination node. The data packet from the source node is then forwarded to the destination node via the minimum hop route, typically via these various intermediate nodes. If any data transfer link is broken in between the source and destination, such as by a device leaving the mobile ad hoc network, an intermediate node generates and forwards a Route Error (“RERR”) packet to the neighboring nodes, destined for the source node. Upon receiving a RERR packet, each node erases or otherwise removes the route containing the nonfunctioning link. Upon receiving such a RERR packet, the source node may attempt to retransmit the data packet using another route to the destination node which it may have cached from previous route discovery sessions, or can start another route discovery session to find a new route to the destination nodes. As a result of such repetition, network congestion is further increased, wasting time and increasing the overhead cost of the mobile ad hoc network.
Accordingly, a need remains for a system, apparatus and method for an on-demand routing protocol for a mobile ad hoc network which reduces the potential for such network congestion. Such a system, apparatus, method and software for such a routing protocol should also be reasonably scalable, reliable, and efficient, thereby reducing routing overhead and reducing the likelihood of dropped or corrupted data packets.